1485B - Replace and Keep Sorted - CodeForces Solution

// © Urvish Patel

#include<bits/stdc++.h>
using namespace std;

#define fast  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

#define ll long long int

#define endll "\n"

#define f(var,srt,ed) for(int var=srt;var<ed;var++)
#define rf(var,srt,ed) for(int var=srt;var>ed;var--)
#define fe(var,cont) for(auto &var:cont)

#define pb push_back
#define begin begin()
#define end end()

#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) ((a*b)/(__gcd(a,b)))

#define YES(x) cout<<"YES"<<x
#define NO(x) cout<<"NO"<<x

ll dp[(int)1e5+2][4];
//0 none, 1 left, 2 right, 3 both


void solve()
{
    int n,q,k;
    cin>>n>>q>>k;

    int arr[n];

    f(i,0,n)
    cin>>arr[i];

    f(i,0,n)
    {
        int left,right;

        if(i==0)
        {
            left=0;
            right=arr[i+1];

            dp[i][0]=k-1;
            dp[i][1]=k-left-1;
            dp[i][2]=right-2;
            dp[i][3]=right-left-2;
        }
        else if(i==n-1)
        {
            right=0;
            left=arr[i-1];

            dp[i][0]=k-1;
            dp[i][1]=k-left-1;
            dp[i][2]=right-2;
            dp[i][3]=right-left-2+dp[i-1][3];
        }
        else
        {
            left=arr[i-1];
            right=arr[i+1];

            dp[i][0]=k-1;
            dp[i][1]=k-left-1;
            dp[i][2]=right-2;
            dp[i][3]=right-left-2+dp[i-1][3];
        }
    }

    // f(i,0,n)
    // {
    //     f(j,0,4)
    //     cout<<dp[i][j]<<" ";

    //     cout<<endl;
    // }

    while(q--)
    {
        int l,r;
        cin>>l>>r;

        int answer=0;

        if(l==r)
        {
            answer+=dp[l-1][0];
        }
        else if(r==l+1)
        {
            answer+=dp[l-1][2];
            answer+=dp[r-1][1];
        }
        else
        {
            answer+=dp[l-1][2];
            answer+=dp[r-1][1];
            answer+=dp[r-2][3]-dp[l-1][3];
        }

        cout<<answer<<endl;
    }

}


int main()
{
    fast

    int t=1;
    //cin>>t;

    f(_,0,t)
    {
        //cout<<"Case #"<<_<<": ";
        solve();
    }




    return 0;
}